|
KMID : 0380319920490000025
|
|
Journal of Korean Research Institute for Better Living
1992 Volume.49 No. 0 p.25 ~ p.34
|
|
|
A Heuristic Algorithm for Reconstructing the Minmax Degree-Constrained Triangulation
|
|
|
|
|
Abstract
|
|
|
Given a set S of n points in the plane, a heuristic algorithm to construct the triangulation that minimizes the maximum degree of points is presented, where the degree of a point is the number of points adjacent to it.
For minimizing the maximum degree, the degrees of points incident to the edge which is shared by two triangles are examined. The original edge between two points is swapped with the new edge according to the index criteria of these points. Also, the point insertion method can be used if the edge swapping cannot be applicable any more because of the distribution of points. This method inserts some additional points in the triangles which have the point as a vertex exceeding the lowerbound of the degree.
|
|
|
KEYWORD
|
|
|
|
|
|
FullTexts / Linksout information
|
|
|
|
|
|
Listed journal information
|
|
|
|